// https://www.lintcode.com/problem/number-of-lines-to-write-string/

public class Solution {
    /**
     * @param widths: an array
     * @param S: a string
     * @return: how many lines have at least one character from S, and what is the width used by the last such line
     */
    public int[] numberOfLines(int[] widths, String S) {
        // Write your code here
        int[] ret = new int[2];
        int lines = 0, steps = 0, width = 0;
        for (int i = 0; i < S.length(); ++i) {
            int c = S.charAt(i) - 'a';
            if ((width + widths[c]) > 100) {
                ++lines;
                width = widths[c];
            } else {
                width += widths[c];
            }
            steps = width;
        }
        ret[0] = lines + 1;
        ret[1] = steps;
        return ret;
    }
}